package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/description/">二叉树的第K大 层和</a>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/2/23 10:06
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode2583 {
    public static long kthLargestLevelSum(TreeNode root, int k) {
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        List<Long> levelSumArray = new ArrayList<>();
        while (!queue.isEmpty()){
            List<TreeNode> levelNodes = new ArrayList<TreeNode>(queue);
            long levelSum = 0;
            queue.clear();
            for (TreeNode node : levelNodes) {
                levelSum += node.getVal();
                if (node.getLeft() != null){
                    queue.offer(node.getLeft());
                }
                if (node.getRight() != null){
                    queue.offer(node.getRight());
                }
            }
            levelSumArray.add(levelSum);
        }
        if (levelSumArray.size() < k) {
            return -1;
        }
        return levelSumArray.get(levelSumArray.size() - k);
    }
}
